//leetcode第67题
class Solution {
public:
    string addBinary(string a, string b) {
        int start1=0,start2=0;
        while(start1<a.size()&&a[start1]=='0')start1++;
        while(start2<b.size()&&b[start2]=='0')start2++;
        if(start1==a.size()&&start2==b.size())return "0";
        int len1=a.size(),len2=b.size();
        if(len1!=len2)
        {
            if(len1>len2)
                for(int i=0;i<len1-len2;i++)
                    b.insert(b.begin(),'0');
            else
                for(int i=0;i<len2-len1;i++)
                    a.insert(a.begin(),'0');
        }
        string s;
        s.resize(a.size()+1,'0');

        int carry=0;
        for(int i=a.size()-1;i>=0;i--)
        {
            int here=(a[i]-'0')+(b[i]-'0')+carry;
            s[i+1]=here%2+'0';
            carry=here/2;
        }
        s[0]=carry+'0';
        if(s[0]=='0')return s.substr(1);
        else return s;
    }
};
